1. Field of the Invention
This invention relates to planarizing a set of overlapping objects, and more particularly to color trapping in electronic printing systems.
2. Description of Related Art
For many years, the preferred process for color printing on paper has been to process the page in multiple exposures, or separations. Each separation exposes selected areas of the paper to an ink of a different color. The usual process ink colors are cyan, magenta, yellow and "key" (CMYK), where key is usually black. Additional color inks are often used as spot colors in additional separations.
High-quality printing, such as that required by the publishing industry, poses many difficult problems in controlling the separations. For example, color printing is compromised if paper is not properly aligned as the paper makes multiple passes through the plates of a printer. As a result, the several inks are never perfectly aligned with one another, and a small gap between regions of different colors may occur, which is often quite visible to the eye as an off-color line. This problem is typically referred to as misregistration.
One common solution to the registration problem is to perform a technique known as "trapping". As color separations are generated, regions of lighter color may be expanded or "spread" beyond their nominal boundaries, while regions of darker color may be contracted or "choked" within such boundaries to create an overlap of colors on the second and subsequent ink passes. The overlap mitigates the effects of misregistration. Trapping techniques have traditionally been performed manually. Although tedious, in the past, manual trapping techniques have been used in applications such as magazine publishing, where the time and labor required to create individual traps for each printed page are economically justified, or in packaging, where the quality of print is important.
In recent years, a new class of low-cost applications in the publishing industry have emerged, namely "desktop" publishing. A desktop publishing system user typically uses a standard personal computer to specify an output page as a computer file in a page description language (PDL) such as "Postscript". (Postscript is a trademark of Adobe Systems, Incorporated of Mountain View, Calif.) The PDL file is then typically sent to a PDL-compatible automatic page setter, which interprets the file and renders the several color separations onto film for later photolithographic manufacture of offset printing plates.
In recent years, computer systems that perform trapping electronically have come into widespread use. One approach to electronic trapping is to have the originating program also create traps for the graphics. As an example, in drawing programs such as Aldus Freehand.RTM., a user is allowed to add outlines around objects to accommodate trapping. Trapping approaches at the originating program level are beneficial because additional trapping costs may be eliminated, i.e., it is not necessary to utilize a post-processing program or traditional trapping techniques. However, trapping capabilities in originating programs have typically been very limited. One shortcoming is apparent in situations where the background and/or foreground is formed by a number of differently colored objects. This situation arises, for example, where individual text characters overlap more than one object. Typical originating programs with trapping capabilities tend to handle objects such as text or boxes in a relatively course fashion, such that traps are only able to be applied to an entire text block, or at best an entire character. Thus, the trap results in these instances are less than desirable. Furthermore, because trap parameters (e.g., overlap width) are specific to the characteristics of each printing press, these values are typically not available at the time a document is created, and requiring content creators to have intimate knowledge of press characteristics places an additional burden on users of these programs.
An automated approach, known as "raster trapping", has been to: (1) start with a PDL file defining a page; (2) convert the vector graphics and/or text within the PDL file into a raster (bit mapped) image at a desired output resolution by means of a raster image processor (RIP); and (3) trap the raster image using pixel data comprising the image. The third step usually requires a creation of a separate plane in a frame buffer for each separation. The planes of the frame buffer are then trapped on a pixel-by-pixel basis, and the result used to control printing of each plane's respective color. As will be appreciated, this approach is very memory intensive, and is input/output bound (a problem even with computers having unlimited memory).
Advantages of raster trapping are: (1) the RIP interpreter has already figured out the interaction and color of edges in the frame buffer; and (2) the operations used to find the color transitions are very simple and the complexity of the operation to process a single frame buffer pixel is constant (i.e., it is a localized operation). Disadvantages of raster based trapping are: (1) the entire frame buffer must be rendered and examined for color changes; and (2) the frame buffer size increases with the square of the page size and resolution and linearly with the number of inks. These factors impose a high data throughput requirement.
A more recent automated approach is set forth in U.S. Pat. No. 5,295,236, titled "Applying Traps to a Printed Page Specified in a Page Description Language Format" and assigned to the assignee of the present invention. The '236 patent discloses a method and apparatus for electronically trapping a printed color page in a desktop publishing, layout, graphics, or similar applications program. The method translates PDL instructions comprising a printed page into a vector-based format suitable for detection and analysis of edges between color regions in the printed page; creates, according to a set of trapping rules, a set of traps at the color edges; and produces a trap output file that includes the traps expressed in PDL format. When the PDL file is interpreted for printing, the traps are processed in the same manner as the original data.
Advantages of vector based trapping are: (1) virtually any printed page that is expressed in a PDL format may be trapped regardless of the application that originally creates the graphics, i.e., the originating program; (2) generally, the number of edges is relatively small compared to the number of pixels in the frame buffer; and (3) the number of edges is approximately linear with respect to resolution and data are relatively independent of the number of separation inks. Disadvantages of vector based trapping are: (1) the interaction of edges and objects must be determined by the trap engine; and (2) the operations used to process the vectors are relatively complex compared to raster operations, and the complexity involved in processing a single edge increases with the number of edges.
From the above it is clear that the advantages and disadvantages of the two automated approaches are almost mutually exclusive. Indeed, going from simple artwork with sparse edge distributions to complex artwork in which the edge density is high, the performance advantage swings from vector based trapping to raster based trapping.
What is needed is a method and system of automatically trapping pages that is relatively simple in implementation, can process any page, and does not require large memory or processor resources compared to prior methods. The present invention provides such a method and system. The most general implementation of the invention also provides a method for planarizing a set of objects (i.e., reduce a set of overlapping objects to a non-overlapping set of objects).